package com.practice.niuke.new_direct_practice.class04;

/**
 * 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容
 * 量为w。
 * 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
 * 牛牛想知道在总体积不超过背包容量的情况下， 他一共有多少种零食放法(总体积为0也
 * 算一种放法)。
 */
public class Code03_SnacksWays {

	/**
	 * 尝试方法一的主函数
	 *
	 * @param arr 零食的体积数组
	 * @param w 背包容量
	 * @return int
	 */
	public static int ways1(int[] arr, int w) {
		// 还剩w容量，可以在arr[0...]自由选择零食，返回选择方案数
		return process(arr, 0, w);
	}

	/**
	 * 尝试方法一（从左往右依次尝试模型）：
	 * 还剩的容量是rest， 可以在arr[index...]自由选择零食，返回选择方案数。
	 * index的变化范围：0~N
	 * rest的变换范围：0~w
	 *
	 * @param arr 零食的体积数组
	 * @param index arr[index...]自由选择零食
	 * @param rest 还剩的容量是rest
	 * @return int
	 */
	public static int process(int[] arr, int index, int rest) {
		if (rest < 0) {// 没有容量了
			// -1表示无方案
			return -1;
		}
		// rest>=0
		if (index == arr.length) {// 无零食可选了
			// 之前的所有决策构成一种方案
			return 1;
		}
		// inex号零食，要 or 不要
		// (index, rest)依赖（index+1, rest）,(index+1, rest-arr[index])
		// 要index号零食
		int next1 = process(arr, index + 1, rest);
		// 不要index号零食
		int next2 = process(arr, index + 1, rest - arr[index]);
		return next1 + (next2 == -1 ? 0 : next2);

	}

	/**
	 * 尝试方法一的dp改写
	 *
	 * @param arr 零食的体积数组
	 * @param w 背包容量
	 * @return int
	 */
	public static int ways2(int[] arr, int w) {
		int N = arr.length;
		int[][] dp = new int[N + 1][w + 1];
		for (int j = 0; j <= w; j++) {
			dp[N][j] = 1;
		}
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j <= w; j++) {
				dp[i][j] = dp[i + 1][j] + ((j - arr[i] >= 0) ? dp[i + 1][j - arr[i]] : 0);
			}
		}
		return dp[0][w];
	}

	/**
	 * 尝试方法二：
	 * f(i, b): arr[0...i]零食自由选择，但是选择所凑出来的体积必须严格为b
	 *
	 * @param arr
	 * @param w
	 * @return
	 */
	public static int ways3(int[] arr, int w) {
		int N = arr.length;
		int[][] dp = new int[N][w + 1];
		for (int i = 0; i < N; i++) {
			dp[i][0] = 1;
		}
		if (arr[0] <= w) {
			dp[0][arr[0]] = 1;
		}
		for (int i = 1; i < N; i++) {
			for (int j = 1; j <= w; j++) {
				dp[i][j] = dp[i - 1][j] + ((j - arr[i]) >= 0 ? dp[i - 1][j - arr[i]] : 0);
			}
		}
		int ans = 0;
		for (int j = 0; j <= w; j++) {
			ans += dp[N - 1][j];
		}
		return ans;
	}

	public static void main(String[] args) {
		int[] arr = { 4, 3, 2, 9 };
		int w = 8;
		System.out.println(ways1(arr, w));
		System.out.println(ways2(arr, w));
		System.out.println(ways3(arr, w));

	}

}
